#include <bits/stdc++.h>
using namespace std;

class Solution {
    public:
        int change(int amount, vector<int>& coins) {
            vector<int> dp(amount + 1);
            dp[0] = 1;
            for (int x : coins) {
                for (int j = x; j <= amount; j++) {
                    if(dp[j] < INT_MAX-dp[j-x])
                        dp[j] += dp[j-x];
                }
            }
            return dp[amount];
        }
    };